Show that \({2^n} \equiv {( - 1)^n}(\bmod 3)\), where \(n \in \mathbb{N}\).

Hence show that an integer is divisible by 3 if and only if the difference between the sum of its binary (base 2) digits in even-numbered positions and the sum of its binary digits in odd-numbered positions is divisible by 3.

Express the hexadecimal (base 16) number \({\text{ABB}}{{\text{A}}_{{\text{16}}}}\) in binary.

Find \({H_2}\), \({H_3}\) and \({H_4}\).

Conjecture a formula for \({H_n}\) in terms of \(n\), for \(n \in {\mathbb{Z}^ + }\).

Prove by mathematical induction that your formula is valid for all \(n \in {\mathbb{Z}^ + }\).

Find the general solution to this equation.

Hence find the solution with minimum positive value of \(xy\).

Find the solution satisfying \(xy = 2014\).

A number written in base 5 is 4303. Find this as a number written in base 10.

1000 is a number written in base 10. Find this as a number written in base 7.

Without attempting to draw \(J\), verify that J satisfies the handshaking lemma;

Without attempting to draw \(J\), determine the number of faces in \(J\).

The vertices D and G are joined by a single edge to form the graph \(K\). Show that \(K\) is not planar.

Explain why a graph containing a cycle of length three cannot be bipartite. 

Hence by finding a cycle of length three, show that the complement of \(K\) is not bipartite.

Use the Euclidean algorithm to find the greatest common divisor of 74 and 383.

Hence find integers s and t such that 74s + 383t = 1.

Given that \(a \equiv b(\bmod p)\) , show that \({a^n} \equiv {b^n}(\bmod p)\) for all \(n \in {\mathbb{Z}^ + }\) .

Show that \({29^{13}} + {13^{29}}\) is exactly divisible by \(7\).

Find the general solution to the Diophantine equation \(3x + 5y = 7\).

Find the values of \(x\) and \(y\) satisfying the equation for which \(x\) has the smallest positive integer value greater than \(50\).

Consider the linear congruence \(ax \equiv b(\bmod p)\) where \(a,{\text{ }}b \in {\mathbb{Z}^ + },{\text{ }}p\) is a prime and \(\gcd (a,{\text{ }}p) = 1\). Using Fermat’s little theorem, show that \(x \equiv {a^{p - 2}}b(\bmod p)\).

Hence find the smallest value of \(x\) greater than 100 satisfying the linear congruence \(3x \equiv 13(\bmod 19)\).

Use the Euclidean algorithm to find \(\gcd (162,{\text{ }}5982)\).

The relation \(R\) is defined on \({\mathbb{Z}^ + }\) by \(nRm\) if and only if \(\gcd (n,{\text{ }}m) = 2\).

(i)     By finding counterexamples show that \(R\) is neither reflexive nor transitive.

(ii)     Write down the set of solutions of \(nR6\).

Express the number \(47502\) as a product of its prime factors.

The positive integers \(M\) , \(N\) are such that \(\gcd (M,N) = 63\) and \(lcm(M,N) = 47502\) . Given that \(M\) is even and \(M < N\) , find the two possible pairs of values for \(M\) , \(N\) .

Solve the recurrence relation \({u_n} = 4{u_{n - 1}} - 4{u_{n - 2}}\) given that \({u_0} = {u_1} = 1\).

Consider \({v_n}\) which satisfies the recurrence relation \(2{v_n} = 7{v_{n - 1}} - 3{v_{n - 2}}\) subject to the initial conditions \({v_0} = {v_1} = 1\).

Prove by using strong induction that \({v_n} = \frac{4}{5}{\left( {\frac{1}{2}} \right)^n} + \frac{1}{5}{\left( 3 \right)^n}\) for \(n \in \mathbb{N}\).

Prove that \(3k + 2\) and \(5k + 3\) , \(k \in \mathbb{Z}\) are relatively prime.

Prove that the number \(14 641\) is the fourth power of an integer in any base greater than \(6\).

For \(a,b \in \mathbb{Z}\) the relation \(aRb\) is defined if and only if \(\frac{a}{b} = {2^k}\) , \(k \in \mathbb{Z}\) .

  (i)     Prove that \(R\) is an equivalence relation.

  (ii)     List the equivalence classes of \(R\) on the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

Using mathematical induction or otherwise, prove that the number \({(1020)_n}\) , that is the number \(1020\) written with base \(n\) , is divisible by \(3\) for all values of \(n\) greater than \(2\).

Explain briefly why the case \(n = 2\) has to be excluded.

Prove that if \({\rm{gcd}}(a,b) = 1\) and \({\rm{gcd}}(a,c) = 1\) , then \({\rm{gcd}}(a,bc) = 1\) .

(i)     A simple graph has e edges and v vertices, where \(v > 2\) . Prove that if all the vertices have degree at least k , then \(2e \ge kv\) .

(ii)     Hence prove that every planar graph has at least one vertex of degree less than 6.

Determine whether or not \(G\) is bipartite.

(i)     Write down the adjacency matrix for \(G\).

(ii)     Find the number of distinct walks of length \(4\) beginning and ending at A.

Use the Euclidean Algorithm to show that \(275\) and \(378\) are relatively prime.

Find the general solution to the diophantine equation \(275x + 378y = 1\) .

In base \(5\) an integer is written \(1031\). Express this integer in base \(10\).

Given that \(N = 365,{\text{ }}r = 10\) and \(s = 7\) find the values of \({a_0},{\text{ }}{a_1},{\text{ }}{a_2},{\text{ }} \ldots \).

(i)     Given that \(N = 899,{\text{ }}r = 10\) and \(s = 12\) find the values of \({a_0},{\text{ }}{a_1},{\text{ }}{a_2},{\text{ }} \ldots \)

(ii)     Hence write down the integer in base \(12\), which is equivalent to \(899\) in base \(10\).

Show that \(121\) is always a square number in any base greater than \(2\).

(i)     Use the Euclidean algorithm to find gcd(\(6750\), \(144\)) .

(ii)     Express your answer in the form \(6750r + 144s\) where r , \(s \in \mathbb{Z}\) .

Consider the base \(15\) number CBA, where A, B, C represent respectively the digits ten, eleven, twelve.

  (i)     Write this number in base \(10\).

  (ii)     Hence express this number as a product of prime factors, writing the factors in base 4.

(i)     Sum the series \(\sum\limits_{r = 0}^\infty  {{x^r}} \) .

(ii)     Hence, using sigma notation, deduce a series for

  (a)     \(\frac{1}{{1 + {x^2}}}\) ;

  (b)     \(\arctan x\) ;

  (c)     \(\frac{\pi }{6}\) .

Show that \(\sum\limits_{n = 1}^{100} {n! \equiv 3(\bmod 15)} \) .

Determine the value of \(b\) .

Find the representation of \(N\)

  (i) in base \(10\);

  (ii) in base \(12\).

Find the positive square root of the base 7 number \({(551662)_7}\), giving your answer as a base 7 number.

(a)     Show that the solution to the linear congruence \(ax \equiv b(\bmod p)\), where \(a,{\text{ }}x,{\text{ }}b,{\text{ }}p \in {\mathbb{Z}^ + },{\text{ }}p\) is prime and \(a\), \(p\) are relatively prime, is given by \(x \equiv {a^{p - 2}}b(\bmod p)\).

(b)     Consider the congruences

     \(7x \equiv 13(\bmod 19)\)

     \(2x \equiv 1(\bmod 7)\).

(i)     Use the result in (a) to solve the first congruence, giving your answer in the form \(x \equiv k(\bmod 19)\) where \(1 \leqslant k \leqslant 18\).

(ii)     Find the set of integers which satisfy both congruences simultaneously.

Given that \({n^2} + 2n + 3 \equiv N(\bmod 8)\) , where \(n \in {\mathbb{Z}^ + }\) and \(0 \le N \le 7\) , prove that \(N\) can take one of only three possible values.

A sequence \(\left\{ {{u_n}} \right\}\) satisfies the recurrence relation \({u_{n + 2}} = 2{u_{n + 1}} - 5{u_n}\) , \(n \in \mathbb{N}\) . Obtain an expression for \({u_n}\) in terms of n given that \({u_0} = 0\) and \({u_1} = 1\) .

(ii)     Find the number of walks of length \(4\) beginning and ending at B.

(i)     Draw \(G'\), the complement of \(G\) .

(ii)     Write down the degrees of all the vertices of \(G\) and all the vertices of \(G'\).

(iii)     Hence, or otherwise, determine whether or not \(G\) and \(G'\) are isomorphic.

Draw the simple graph \(G\).

Explain why \(G\) does not contain an Eulerian circuit.

Show that \(G\) has a Hamiltonian cycle.

State whether or not \(G\) is planar, giving a reason for your answer.

State whether or not the simple graph \(G\) is bipartite, giving a reason for your answer.

Draw the complement \(G'\) of \(G\).